We present a statistically consistent algorithm for constrained classification problems where the objective (e.g.

Summary and Contributions: The paper proposes a novel approach to learning a multiclass classifier under structural constraints motivated from fairness applications. The performance of a candidate classifier h -- a general mapping of the feature space on a probability simplex -- is measured through the so-called confusion matrix'' C[h] whose vectorization stacks the vector of expected sufficient statistics extracted from a datapoint (X,Y) and the classifier output \hat Y . The goal is then to solve a convex program, where a smooth and convex los is minimized over the set of achievable confusion matrices, corresponding to the fixed (and unknown to the learner) population distribution, under a number of (convex) functional constraints. This setup has been earlier considered by Narasimkhan (2018). The authors advocate the following approach: the problem is cast as convex program with smooth objective, and with constraint set given as the intersection of the two sets (of confusion matrices): - the feasible'' set \F corresponding to the functional constraints; - the achievable'' set \C corresponding to all possible confusion matrices for the data-generating distribution.

We present a statistically consistent algorithm for constrained classification problems where the objective (e.g. The key idea is to reduce the problem into a sequence of plug-in classifier learning problems, which is done by formulating an optimization problem over the intersection of the set of achievable confusion matrices and the set of feasible matrices. For objective and constraints that are convex functions of the confusion matrix, our algorithm requires O(1/\epsilon 2) calls to the plug-in routine, which improves on the O(1/\epsilon 3) rate achieved by Narasimhan (2018). We demonstrate empirically that our algorithm performs at least as well as the state-of-the-art methods for these problems.